package base.Chapter01_Sort;

import java.util.Arrays;

import static utils.CommonUtils.*;

/**
 * 插入排序逻辑:
 * 1, 从左到右分为已排序和未排序两个区间;
 * 2, 在未排序区间拿一个元素, 与已排序区间的数做对比(从右到左)
 * 3, 如果已排序的大, 则向右挪一个位置
 * 4, 直到找到已排序的区间的数小于等于未排序数
 * 5, 重新开始2-4
 */
public class C02_InsertionSort {
    public static void sort(int[] arr) {
        //1, 数据合法性检验
        if (arr == null || arr.length <= 1) {
            return;
        }
        //2, 排序逻辑
        //2.1 遍历未排序区间, 取数
        for (int i = 1; i < arr.length; i++) {
            //2.2 遍历已排序区间, 比较
            for (int j = i; j > 0; j--) {
                if (arr[j - 1] > arr[j]) {
                    swap(arr, j - 1, j);// 执行交换
                } else {
                    break;// 跳出本轮循环
                }
            }
        }
    }

    /**
     * 执行校验
     */
    public static void main(String[] args) {
        int[] arr = {19, 100, 50, 4, 1};
        sort(arr);
        Arrays.stream(arr).mapToObj(e->e+" ").forEach(System.out::print);
    }
}
